Un autómata celular (A.C.) es un modelo matemático y computacional para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.

Es un modelo matemático para un sistema dinámico que consiste en una rejilla formada por celdas que pueden cambiar de estado o no dependiendo diversas leyes. Es un espacio regular. Tiene un conjunto de estados finito y cada elemento toma un valor de este conjunto de estados. Presenta una función de transición local que es la regla de evolución que determina el comportamiento del autómata.

La definición de un A.C. requiere mencionar sus elementos básicos:

• Un espacio regular: Ya sea una línea, un plano de 2 dimensiones o un espacio n-dimensional. Cada división homogénea del espacio es llamada célula.
• Conjunto de Estados: Es finito y cada elemento o célula del espacio toma un valor de este conjunto de estados. También se denomina alfabeto. Puede ser expresado en valores o colores.
• Configuración Inicial: Es la asignación inicial de un estado a cada una de las células del espacio.
• Vecindades: Define el conjunto de células que se consideran adyacentes a una dada, así como la posición relativa respecto a ella. Cuando el espacio es uniforme, la vecindad de cada célula es isomorfa (es decir, que tiene el mismo aspecto).
• Función de Transición Local: Es la regla de evolución que determina el comportamiento del A.C. Se calcula a partir del estado de la célula y su vecindad. Define cómo debe cambiar de estado cada célula dependiendo su estado anterior y de los estados anteriores de su vecindad. Suele darse como una expresión algebraica o un grupo de ecuaciones.

Se clasifican principalmente de la siguiente manera:

• Clase I: Lleva a un estado homogéneo perdiendo la aleatoriedad del estado inicial.
• Clase II: Se generan estructuras cíclicas, separadas y simples. Los cambios en la configuración inicial sólo afectan una región finita de células cercanas
• Clase III: Casi todos los patrones iniciales evolucionan de forma caótica. Los cambios en la configuración inicial tienden a propagarse indefinidamente.
• Clase IV: Se producen estructuras complejas no explicadas por las clases anteriores. Tienen combinación de patrones cíclicos y comportamiento aleatorio

Son sistemas descubiertos dentro del campo de la física computacional por John von Neumann en la década de 1950. La teoría de los autómatas celulares se inicia con su precursor John von Neumann a finales de la década de 1940 con su libro Theory of Self-reproducing Automata (editado y completado por A. W. Burks).

Aunque John von Neumann puso en práctica los AA.CC., estos fueron concebidos en los años 40 por Konrad Zuse y Stanislaw Ulam. Zuse pensó en los “espacios de cómputo” (computing spaces), como modelos discretos de sistemas físicos. Las contribuciones de Ulam vinieron al final de los 40, poco después de haber inventado con Nicholas Metropolis el Método de Montecarlo.